#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;

vector<pair<int, int>> G[MAXN * 2];

// G[u]: 存所有以u为起点的边的信息，(v,w); u->v, w

void addedge(int u, int v, int w) {
    G[u].emplace_back(v, w);
}

int n, m, x;
bool used[MAXN * 2];
long long dis[MAXN * 2];

int main() {
    // i <-> i+n
    scanf("%d%d%d", &n, &m, &x);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v, 1);
        addedge(v + n, u + n, 1);
    }
    for (int i = 1; i <= n; ++i) {
        addedge(i, i + n, x);
        addedge(n + i, i, x);
    }

    priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                   greater<pair<long long, int>>>
        q;
    for (int i = 1; i <= 2 * n; ++i)
        dis[i] = 1e18;
    q.push({dis[1] = 0, 1});

    while (!q.empty()) {
        auto [_, v] = q.top();
        q.pop();
        if (used[v])
            continue;
        used[v] = true;

        for (auto [to, w] : G[v]) {
            if (dis[to] > dis[v] + w) {
                dis[to] = dis[v] + w;
                q.push({dis[to], to});
            }
        }
    }
    printf("%lld\n", min(dis[n], dis[2 * n]));

    return 0;
}